/*
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。



*/

//两次遍历
class Solution
{
public:
    vector<TreeNode *> getPath(TreeNode *root, TreeNode *target)
    {
        vector<TreeNode *> path;
        TreeNode *node = root;
        while (node != target)
        {
            path.push_back(node);
            if (target->val < node->val)
            {
                node = node->left;
            }
            else
            {
                node = node->right;
            }
        }
        path.push_back(node);
        return path;
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        vector<TreeNode *> path_p = getPath(root, p);
        vector<TreeNode *> path_q = getPath(root, q);
        TreeNode *ancestor;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i)
        {
            if (path_p[i] == path_q[i])
            {
                ancestor = path_p[i];
            }
            else
            {
                break;
            }
        }
        return ancestor;
    }
};

//一次遍历
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        TreeNode *ancestor = root;
        while (true)
        {
            if (p->val < ancestor->val && q->val < ancestor->val)
            {
                ancestor = ancestor->left;
            }
            else if (p->val > ancestor->val && q->val > ancestor->val)
            {
                ancestor = ancestor->right;
            }
            else
            {
                break;
            }
        }
        return ancestor;
    }
};
